package 面试代码;

/**二分查找的几种常用版本
 * 注意搜索区间和while的终止条件,如果存在漏掉的元素,记得在最后检查!
 * @author zx
 * @create 2022-03-17 14:43
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] nums = {1,2,3,5,6,6,6,6,6,7,8,9};
        int target = 5;
        int res = binarySearch(nums,target);
        System.out.println(res);
    }
    /**
     * @return 寻找一个数(基本的二分搜索)
     * //搜索区间：[left, right]
     * //终止条件是 left == right + 1,写成区间的形式就是 [right + 1, right],
     * //或者带个具体的数字进去 [3, 2],可见这时候区间为空
     * 当发现索引mid不是要找的target时,下一步应该去搜索[left, mid-1]或[mid+1, right];
     * 因为mid已经搜索过，应该从搜索区间中去除。
     */
    public static int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target){
                return mid;
            } else if (nums[mid] < target){
                left = mid + 1; //注意
            } else if (nums[mid] > target){
                right = mid - 1; //注意
            }
        }
        return -1;
    }

    /**
     * [1,2,3,4,5,6,6,6,6,6,7,8,9] 即下标为5的6(eg:leetcode_34)
     * @return 寻找左侧边界的二分搜索
     * 要让搜索区间两端都闭,所以right应该初始化为nums.length - 1,
     * while的终止条件应该是left == right + 1,也就是其中应该用<=
     * 由于while的退出条件是left == right + 1,所以当target比nums中所有元素都大时,会使得索引越界
     * 因此,最后返回结果的代码应该检查越界情况:left >= nums.length
     * 当target比nums中所有元素都小时,(left == 0 && nums[left] != target)
     */
    public static int leftBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        // 搜索区间为 [left, right]
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] < target) {
                // 搜索区间变为 [mid+1, right]
                left = mid + 1;
            } else if (nums[mid] > target) {
                // 搜索区间变为 [left, mid-1]
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 收缩右侧边界
                right = mid - 1;
            }
        }
        // 检查出界情况(待查找集合中不存在target)
        if (left >= nums.length || nums[left] != target){
            return -1;
        }
        return left;
    }

    /**
     * [1,2,3,4,5,6,6,6,6,6,7,8,9] 即下标为9的6(eg:leetcode_34)
     * @return 寻找右侧边界的二分查找
     * while循环的终止条件是left == right
     * while循环结束时,nums[left]一定不等于target了,而nums[left-1]可能是target
     * 当target比所有元素都小时,right会被减到-1,所以需要在最后防止越界
     */
    public static int rightBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 这里改成收缩左侧边界即可
                left = mid + 1;
            }
        }
        // 这里检查right越界的情况(待查找集合中不存在target)
        if (right < 0 || nums[right] != target){
            return -1;
        }
        return right;
    }

    /**
     * {1,2,3,5,6,6,6,6,6,7,8,9},target = 4  找到3
     * @return 找到最接近target的小于值(待查找的集合中没有target)
     * eg：x的平方根_69
     */
    public static int lessTarget(int[] nums, int target){
        int left = 0,right = target;
        int res = -1;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(nums[mid] <= target){
                res = nums[mid];
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }
        }
        return res;
    }

    /**
     * {1,2,3,5,6,6,6,6,6,7,8,9},target = 4  找到5
     * @return 找到最接近target的大于值(待查找的集合中没有target)
     * eg：搜索插入位置_35
     */
    public static int greaterTarget(int[] nums, int target){
        int left = 0,right = target;
        int res = -1;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] >= target){
                res = nums[mid];
                right = mid - 1;
            }
        }
        return res;
    }
}
